#ifndef __SUFFIX_TREE_H__
#define __SUFFIX_TREE_H__ 1

#include <vector>
#include <algorithm>
#include <iostream>
#include <cassert>

// here we supposed that the size of alphabet
// fits constraints [1..256]

template < int Alph >
struct SuffixTree
{
    // 0 - fictive vertex
    // 1 - root
    
    enum
    {
        PRE_ROOT = 0,
        ROOT = 1,
        EMPTY = -10,
        ERROR = -5
    };

    struct List
    {
        size_t start_pos; // 0 - based index
        size_t end_pos;   // [start_pos, end_pos)
                       // when end_pos == (size_t) -1, int refers to list
        int parent;
        int suf_link; // valid only to inner vertices,
                      // when invalid, refers to -1-th vertex
        int next[Alph]; // pointers to marked children

        void
        set_value(int val)
        {
            std::fill(next, next + Alph, val);
        }

        void
        clear()
        {
            set_value(EMPTY);
        }

        List()
        {
            start_pos = 0;
            end_pos = 0;
            parent = -1;
            suf_link = -1;
            clear();
        }
    };

    struct ActiveNode
    {
        int go; // vertex, what you go to
        int processed; // number of symbols read on parent's edge
        ActiveNode() : go(0), processed(0)
        {}
    };

    std::vector < int > str;
    std::vector < List > __tree;
    size_t size;
    size_t str_len;
    ActiveNode active_node_pos;

    int
    edge_len(const int x)
    {
        return std::min(__tree[x].end_pos, str_len) - __tree[x].start_pos;
    }

    void
    inc_size()
    {
        ++size;
        if (__tree.size() == size) {
            __tree.push_back(List());
        }
    }

    int can_go(const ActiveNode &, int);
    void go(ActiveNode &, int);
    void cut_edge(ActiveNode &);
    void add_ver(int, int, int);
    void make_suf_link(int, int);
    void add_elem(int);
    void init();
    SuffixTree(); 
    ~SuffixTree();
    SuffixTree(const char *);
    void output_data();
};

template < int Alph >
int
SuffixTree< Alph >::can_go(
        const SuffixTree< Alph >::ActiveNode &pos,
        int next_char)
{
    int next_vertex = pos.go;
    int distance_to_go = pos.processed;
    if (distance_to_go == edge_len(next_vertex)) {
        return __tree[next_vertex].next[next_char];
    }
    if (str[__tree[next_vertex].start_pos + distance_to_go] != next_char) {
        return EMPTY;
    }
    return ERROR;
}

template < int Alph >
void
SuffixTree< Alph >::go(SuffixTree< Alph >::ActiveNode &pos, int next_char)
{
    if (pos.processed == edge_len(pos.go)) {
        pos.go = __tree[pos.go].next[next_char];
        pos.processed = 1;
    } else {
        ++pos.processed;
    }
}

template < int Alph >
void
SuffixTree< Alph >::cut_edge(SuffixTree< Alph >::ActiveNode &pos)
{
    inc_size();
    __tree[size].start_pos = __tree[pos.go].start_pos;
    __tree[size].end_pos = __tree[pos.go].start_pos + pos.processed;
    __tree[size].parent = __tree[pos.go].parent;
    __tree[size].clear();
    int left_border = __tree[size].start_pos;
    __tree[__tree[size].parent].next[str[left_border]] = size;
    left_border = std::min(__tree[size].end_pos, str_len);
    __tree[size].next[str[left_border]] = pos.go;
    __tree[pos.go].start_pos = left_border;
    __tree[pos.go].parent = size;
    pos.go = size;
    pos.processed = edge_len(size);
}

template < int Alph >
void
SuffixTree< Alph >::add_ver(int cur_ver, int pos, int next_char)
{
    inc_size();
    __tree[size].start_pos = pos;
    __tree[size].end_pos = (size_t) -1;
    __tree[size].parent = cur_ver;
    __tree[size].clear();
    __tree[cur_ver].next[next_char] = size;
}

template < int Alph >
void
SuffixTree< Alph >::make_suf_link(int cur_ver, int pos)
{
    int tmp_ver = __tree[__tree[cur_ver].parent].suf_link;
    int distance = edge_len(cur_ver);
    pos -= distance;
    int stage_distance = edge_len(__tree[tmp_ver].next[str[pos]]);
    // condition: distance >= 0 always
    while (distance >= stage_distance && distance) {
        tmp_ver = __tree[tmp_ver].next[str[pos]];
        pos += stage_distance;
        distance -= stage_distance;
        if (distance) {
            stage_distance = edge_len(__tree[tmp_ver].next[str[pos]]);
        }
    }
    if (!distance) {
        __tree[cur_ver].suf_link = tmp_ver;
    } else {
        ActiveNode a_node_pos;
        a_node_pos.go = __tree[tmp_ver].next[str[pos]];
        a_node_pos.processed = distance;
        cut_edge(a_node_pos);
        __tree[cur_ver].suf_link = a_node_pos.go;
    }
    __tree[ROOT].suf_link = PRE_ROOT;
}

template < int Alph >
void
SuffixTree< Alph >::add_elem(int next_char)
{
    int cur_pos = str_len;
    ++str_len;
    str.push_back(next_char);
    while (can_go(active_node_pos, next_char) == EMPTY) {
        if (active_node_pos.processed != edge_len(active_node_pos.go)) {
            cut_edge(active_node_pos);
        }
        int cur_ver = active_node_pos.go;
        add_ver(cur_ver, cur_pos, next_char);
        make_suf_link(cur_ver, cur_pos);
        active_node_pos.go = __tree[cur_ver].suf_link;
        active_node_pos.processed = edge_len(active_node_pos.go);
    }
    if (can_go(active_node_pos, next_char) != EMPTY) {
        go(active_node_pos, next_char);
    }
}

template < int Alph >
void
SuffixTree< Alph >::init()
{
    str_len = 0;
    size = 0;
    __tree.push_back(List());
    inc_size();
    __tree[ROOT].start_pos = -1;
    active_node_pos.go = ROOT;
    active_node_pos.processed = 1;
    __tree[PRE_ROOT].set_value(ROOT);
    __tree[ROOT].parent = PRE_ROOT;
    __tree[ROOT].suf_link = PRE_ROOT;
    __tree[PRE_ROOT].suf_link = PRE_ROOT;
}

template < int Alph >
SuffixTree< Alph >::SuffixTree()
{
    init();
}

template < int Alph >
SuffixTree< Alph >::SuffixTree(const char *str)
{
    init();
    for (; *str; ++str) {
        add_elem(*str - 'a');
    }
}

template < int Alph >
SuffixTree< Alph >::~SuffixTree()
{}

template < int Alph >
void
SuffixTree< Alph >::output_data()
{
    std::cout << size << ' ' << (size - 1) << '\n';
    for (size_t i = 2; i <= size; ++i) {
        std::cout << __tree[i].parent << ' ' << i << ' ' 
            << __tree[i].start_pos << ' ' << (std::min(__tree[i].end_pos, str_len) - 1) << ' ';
        for (size_t it = __tree[i].start_pos; it < std::min(__tree[i].end_pos, str_len); ++it) {
            std::cout << char(str[it] + 'a');
        }
        std::cout << '\n';
    }
    std::cout << "active node = " << active_node_pos.go << ", " <<
        active_node_pos.processed << '\n';
}

#endif
